package com.lsa.letcode.the74.search2dMatrix;

public class Solution {
    /**
     * @param matrix
     * @param t target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int t) {
    	int[] result = searchMatrixIdx(matrix, t);
    	return result[0] > -1;
    }
    
    public int[] searchMatrixIdx(int[][] matrix, int t) {
    	int[] result = new int[]{-1, -1};
    	int rCnt = matrix.length;
		if (rCnt == 0) {
    		return result;
    	}
    	else if (matrix[0].length == 0) {
    		return result;
    	}
		int cCnt = matrix[0].length;
    	int idx = binarySearch(matrix, 0, rCnt - 1, t);
    	if (idx > -1) {
    		result[0] = idx;
    		result[1] = 0;
    	}
    	else {
    		int ipt = -idx - 1; // [0 .. size]
    		if (ipt == rCnt) { //[size]
    			idx = binarySearch(matrix[rCnt - 1], 0, cCnt - 1, t);
    			if (idx > -1) {
    				result[0] = rCnt - 1;
    	    		result[1] = idx;
    			}
    		}
    		else if (ipt == 0) { // [0]
    			idx = binarySearch(matrix[0], 0, cCnt - 1, t);
    			if (idx > -1) {
    				result[0] = 0;
    	    		result[1] = idx;
    			}
    		}
    		else { // [1 .. size - 1]
    			idx = binarySearch(matrix[ipt - 1], 0, cCnt - 1, t);
    			if (idx > -1) {
    				result[0] = ipt - 1;
    	    		result[1] = idx;
    			}
    			else { // -1
    				idx = binarySearch(matrix[ipt], 0, cCnt - 1, t);
    				if (idx > -1) {
        				result[0] = ipt;
        	    		result[1] = idx;
        			}
    			}
    		}
    	}
    	return result;
    }
    
    private int binarySearch(int[][] nums, int low, int high, int t) {
		while(low <= high) {
			int mid = (low + high) >> 1;
			if (nums[mid][0] < t) {
				low = mid + 1;
			}
			else if (nums[mid][0] > t){
				high = mid - 1;
			}
			else {
				return mid;
			}
		}
		return -(low + 1);
	}

	private int binarySearch(int[] nums, int low, int high, int t) {
		while(low <= high) {
			int mid = (low + high) >> 1;
			if (nums[mid] < t) {
				low = mid + 1;
			}
			else if (nums[mid] > t){
				high = mid - 1;
			}
			else {
				return mid;
			}
		}
		return -1;
	}
}